package com.backpack;

import java.util.Arrays;

public class TargetSum0111_494 {
    public int findTargetSumWays(int[] nums, int target) {
        //将nums分为加法集合 和 减法集合，
        // 那么 加法集合 + 减法集合 = sum = nums元素总和
        // 加法集合 - 减法集合 = target
        // 所以 sum + target = 2 * 加法集合。

        int sum = Arrays.stream(nums).sum();

        if((sum + target) % 2 ==1) return 0; //不能凑出任何组合 使其公式值为target

        int tar = (sum + target)/2; //加法集合

        if(tar<0) return 0;

        //背包大小为tar
        //dp[i] 表示 装满容量为i的背包 能放的方法有dp[i]种
        int[] dp = new int[tar + 1];

        //初始化
        dp[0] = 1;

        //递推公式：
        // 例如：nums = [1,1,1,1,1]
        // 容量为5
        // 已经有大小为1的物品， 那么有dp[4]种方法 凑成dp[5]
        // 已经有大小为2的物品 那么有dp[3]种方法 凑成dp[5]
        // 已经有大小为3的物品 那么有dp[2]种方法 凑成dp[5]
        // 已经有大小为4的物品 那么有dp[1]种方法 凑成dp[5]
        // 已经有大小为5的物品 那么有dp[0]种方法 凑成dp[5]
        // dp[0]=1;
        // dp[5] = dp[4] + dp[3] + dp[2] + dp[1] + dp[0]

        // dp[j] += dp[j-num[i]]

        for (int i = 0; i < nums.length; i++) {
            for (int j = tar; j >= nums[i]; j--) {
                dp[j] += dp[j-nums[i]];
            }
        }

        return dp[tar];
    }
}
